package com.jin.three;

import java.util.*;
/**
 * 回溯法求解装载方案问题
 * @author Jin
 * @time 2012-12-4下午11:25:09
 */
public class MaxLoading {
	public static int n; // 集装箱数
	public static int weight1; // 第一艘载重量
	public static int bestWeight; // 当前最优载重量
	public static int[] boxArr; // 集装箱重量数组
	public static int[] xx; //
	public static int[] bestxx;

	public static int maxLoadingRE(int[] w, int c, int[] bestx) { // 递归回溯
		n = w.length;
		weight1 = c;
		bestWeight = 0;
		boxArr = w;
		bestxx = bestx;
		xx = new int[n];
		int r = 0; // 剩余集装箱重量，未进行装载的重量
		for (int i = 0; i < n; i++) {
			r += boxArr[i];
		}
		trackback(0, 0, r);
		return bestWeight;
	}

	private static void trackback(int i, int cw, int r) { // 到达层数，目前装载的重量，未装载的重量
		if (i == n) {// 到达叶结点
			for (int j = 0; j < n; j++) {
				bestxx[j] = xx[j];
			}
			bestWeight = cw;
			return; // 只是一次出栈操作，栈非空还要继续执行
		}
		if (cw + boxArr[i] <= weight1) { // 已装载的加上要装载的小于第一个的载重量
			xx[i] = 0; // 0代表装在第一个上，1代表装在第二个上
			trackback(i + 1, cw + boxArr[i], r); // 试图装载下一个集装箱，r是针对第一个装的重量，因此装在第一个里不需要减，但装在第二个时就要减去该重量
		}
		if (r - boxArr[i] > bestWeight) { // 已装载的加上要装载的已经大于第一个的载重量，并且用总的载重量r减去当前要装载的还比最好的载重量大
			xx[i] = 1; // 放到第二个上
			trackback(i + 1, cw, r - boxArr[i]);
		}
	}

	public static int maxLoading(int[] w, int c, int[] bestx) {
		int i = 0; // 当前层
		int n = w.length; // 层总数
		int[] x = new int[n]; // x[0, i]为当前选择路径
		Arrays.fill(x, -1); // 初始化为-1，0表示选择第一个，1表示选择第二个

		int bestw = 0; // 当前最优装载重量
		int[] cw = new int[n]; // 当前载重量
		int[] r = new int[n]; // 剩余集装箱容量
		int tor = 0;
		for (int item : w) {// item取出w中的值，进行相加
			tor += item;
		}
		r[0] = tor;// 要装载的重量
		cw[0] = 0;
		// 搜索子树
		while (i > -1) {
			do {
				x[i] += 1;
				if (x[i] == 0) { // 选择放在第一个（左子树）
					if (cw[i] + w[i] <= c) {
						if (i < n - 1) {
							cw[i + 1] = cw[i] + w[i];
							r[i + 1] = r[i];
						}
						break; // 能放下就直接跳出这个do-while循环
					}
				} else { // 选择放在第二个（右子树）
					if (r[i] - w[i] > bestw) {
						// 剪枝函数，没有最优解好的话x[i]会自增到2，不会进入下面的if (x[i] < 2)
						if (i < n - 1) {
							r[i + 1] = r[i] - w[i];
							cw[i + 1] = cw[i];
						}
						break;
					}
				}
			} while (x[i] < 2); // 对于放不下的在这里判断后才能取右子树
			if (x[i] < 2) {
				if (i == n - 1) {
					for (int j = 0; j < n; j++) {
						bestx[j] = x[j];
					}
					if (x[i] == 0) {
						bestw = cw[i] + w[i];
					} else {
						bestw = cw[i];
					}
				} else {
					i++;
					x[i] = -1;
				}
			} else {// 当x[i]=2时，说明已经遍历完两个叶节点，应向上一层继续遍历其它节点
				i--;
			}
		}
		return bestw;
	}

	public static void main(String[] args) {
		int[] w = { 20, 10, 40 };
		int n = w.length;
		int c = 50;
		int[] bestx = new int[n];
		int bestw = maxLoadingRE(w, c, bestx);
		System.out.println("bestw : " + bestw);
		System.out.println(Arrays.toString(bestx));
	}
}
